/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-07-23
 * Time: 22:11
 */

public class Solution {
    static final int MOD = 1000000007;

    public int numTilings(int n) {
//         dp[i][s] 表示 第 i 列 的状态
//         dp[i][0] 表示 第 i 列 都不填
//         dp[i][1] 表示 第 i 列 只填上面这一块
//         dp[i][2] 表示 第 i 列 只填下面这一块
//         dp[i][3] 表示 第 i 列 全填
        int[][] dp = new int[n + 1][4];
        // 初始化
        dp[0][3] = 1;
        for (int i = 1; i <= n; i++) {
            // 这一列不填, 那么前面这一列肯定全填, 不能有空
            dp[i][0] = dp[i - 1][3];
            // 填上面这一块, 要么是填了一个三个的, 要么两个的
            dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % MOD;
            // 同上面
            dp[i][2] = (dp[i - 1][0] + dp[i - 1][1]) % MOD;
            // 全填, 四种情况都能填进去
            dp[i][3] = (((dp[i - 1][0] + dp[i - 1][1]) % MOD + dp[i - 1][2]) % MOD + dp[i - 1][3]) % MOD;
        }
        return dp[n][3];
    }
}
